#include <iostream>
#include "BinaryTree.h"

// 99.97 %
class Solution
{
  public:
	bool hasPathSum(TreeNode *root, int sum)
	{
		if (!root)
			return false;
		if (!root->left && !root->right)
			return sum == root->val;
		return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
	}
};

using namespace std;
int main()
{
	int arr[] = {5, 4, 11, 7, 0, 0, 2, 0, 0, 0, 8, 13, 0, 0, 4, 0, 1, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	int sum = 22;
	TreeNode *tree = createBinaryTree(arr, n);
	preorderPrint(tree);
	cout << endl;
	cout << Solution().hasPathSum(tree, 22) << endl;
	return 0;
}
